package memory;

public class Exercises4 {
    // 375、猜数字大小II
    int[][] memo;

    public int getMoneyAmount(int n) {
        // 记忆化搜索
        memo = new int[n + 1][n + 1]; // 从1开始需要访问到n
        return dfs(1,n); // 返回钱
    }

    public int dfs(int left,int right) {
        if (left >= right) {
            return 0;
        }
        // 查询备忘录
        if (memo[left][right] != 0) {
            return memo[left][right];
        }
        int ret = Integer.MAX_VALUE;
        for(int head = left;head <= right;head++) {
            int x = dfs(left,head - 1); // 返回head左面胜利的钱
            int y = dfs(head + 1,right); // 返回head右面胜利的钱
            // 我们需要去他们之间的最大值，因为只有它们的钱数的最大值才可以不论走那面都胜利，之后再加上一开始的钱数
            // 之后和我们要返回的值进行比较取最小值，因为要的就是最小值
            ret = Math.min(Math.max(x,y) + head,ret);
        }
        memo[left][right] = ret;
        return ret;
    }
}
